package leetcode.L500;

//leetcode 面试题08.07
import java.util.ArrayList;

public class EX46_T {
    public String[] permutation(String S) {
        int n = S.length();
        int [] used = new int [n];
        ArrayList<String> res = new ArrayList<>();
        StringBuffer temp = new StringBuffer();
        int deep = 0;

        dfs(S,res,used,temp,deep);

        return res.toArray(new String[res.size()]);
    }
    public void dfs(String S,ArrayList<String> res,int [] used,StringBuffer temp,int deep){
        if(deep == S.length()){
            res.add(temp.toString());
            return;
        }
        for (int i = 0; i < S.length() ; i++) {
            if(used[i]==0){
                used[i]=1;
                temp.append(S.charAt(i));
                dfs(S,res,used,temp,deep+1);
                temp.deleteCharAt(temp.length()-1);
                used[i]=0;
            }
        }
    }
}
